iT邦幫忙

2022 iThome 鐵人賽

DAY 19
0
AI & Data

了解AI多一點點系列 第 19

【Day 19】傳教士與食人族 – 函式設計

  • 分享至 

  • xImage
  •  

上回將結點架構給設計完畢了,接著我們要來將一些會重複用到的功能設計成函式,這樣可以讓我們的程式變得簡潔,可讀性也會變得更高。

判斷終點

第一個函式用來判斷是否為終點。設計概念為若右岸的傳教士數和食人族數皆為0,並且A船和B船中至少有一艘位於左岸。
設計結果如下:

# Determine whether the state reach the goal
def isGoal(x):
    if x.m == 0 and x.c == 0 and (x.a == 0 or x.b == 0):
        return True
    else:
        return False

確認節點位置

第二個函式用來確認結點是否在open list之中。每當我們做完結點的展開後,新生成的結點就要放進open list中,之後再根據g值,從最小值者開始進行展開。若展開的結點已經位於open list中,則我們需要確認原先的g值比較小還是新展開的比較小,最終取較小值。
設計結果如下:

# Determine whether the state is in the Open List
def inOpen(x, open):
    for e in open:
        if x.m == e.m and x.c == e.c and x.a == e.a and x.b == e.b:
            return True
    return False

確認節點合法性

第三個函式用來確認新展開的結點是否合法。由於我們的展開方式是直接增減人數並未考慮會不會小於0或是超出原本的人數,因此額外設計此函式來確認是否結點合法,若合法才會新增進list中。
設計結果如下:

# Determine whether the state is legal
def isLegal(bank, boat):
    flag1 = flag2 = flag3 =  False
    if bank.m >= 0 and bank.m <= M and bank.c >= 0 and bank.c <= C:
        if bank.m == 0 or bank.m >= bank.c:
            flag1 = True

    if boat.am >= boat.ac and boat.bm >= boat.bc:
        flag2 = True

    if M - bank.m >= C - bank.c:
        flag3 = True

    return flag1 and flag2 and flag3

提取路徑

第四個函式用來將最終的最短路徑結果從closed list中提取出來。提取的方式就利用到了我們一開始設計結點架構時所保留的編號以及父結點編號,從最後的終點一路回推至起點,如此便得到了這條最佳路徑。
設計結果如下:

# conclude the closed_list to result
def showResult(list):
    result = []
    temp = list[-1]
    result.append(temp)
    while True:
        for e in list:
            if e.num == temp.parent:
                temp = e
                break
        result.append(temp)
        if temp.num == 0:
            break
    return result

Heuristic function

最後一個函式用來設計heuristic function。我們最終的目標是使用者可以選擇使用A*演算法或是Dijkstra演算法去做推導,因此我們此處將版本一設定為A*演算法,版本二設定為Dijkstra演算法,當使用Dijkstra演算法時,heuristic function就設為0。但目前這裡我們做保留將回傳直接設為0,也就是先皆使用Dijkstra演算法,heuristic的設計可以有許多種可能的,只要能夠是低估或相等於真實的剩餘距離皆是可以的,這邊留給讀者們自己設計。只要將版本依流程控管部分改為自己設計的heuristic函式即可。
設計結果如下:

#Heuristic function
def h(s):
    if ("version" == 1):
        return 0
    else:
    return 0

Github連結:https://github.com/Ming06-22/Missionaries-cannibals


上一篇
【Day 18】傳教士與食人族 – 節點架構
下一篇
【Day 20】傳教士與食人族 – 展開結點
系列文
了解AI多一點點30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言